//
// Created by wangxiyue on 2019/8/19.
//

/*
 * @lc app=leetcode.cn id=300 lang=c
 *
 * [300] 最长上升子序列
 *
 * https://leetcode-cn.com/problems/longest-increasing-subsequence/description/
 *
 * algorithms
 * Medium (42.91%)
 * Likes:    251
 * Dislikes: 0
 * Total Accepted:    21.6K
 * Total Submissions: 50.4K
 * Testcase Example:  '[10,9,2,5,3,7,101,18]'
 *
 * 给定一个无序的整数数组，找到其中最长上升子序列的长度。
 *
 * 示例:
 *
 * 输入: [10,9,2,5,3,7,101,18]
 * 输出: 4
 * 解释: 最长的上升子序列是 [2,3,7,101]，它的长度是 4。
 *
 * 说明:
 *
 *
 * 可能会有多种最长上升子序列的组合，你只需要输出对应的长度即可。
 * 你算法的时间复杂度应该为 O(n^2) 。
 *
 *
 * 进阶: 你能将算法的时间复杂度降低到 O(n log n) 吗?
 *
 *
 * 自己测试样本
 * [10,9,2,5,3,7,101,18]
 * [10,9,8,7,6]
 * [1,2,3,4,5,6,7,8,9]
 * [1,2,4,3,10,3,2,11]
 *
 */
#include <stdio.h>

int lengthOfLIS(int *nums, int numsSize) {
    int dp[numsSize];

    dp[0] = 1;
    int max = 1;

    for (int i = 1; i < numsSize; i++) {
        dp[i] = 1;
        /* code */
        for (int j = i - 1; j >= 0; j--) {
            /* code */
            if (nums[i] > nums[j]) {
                if (dp[i] <= dp[j]) {
                    dp[i] = dp[j] + 1;
                }
                max = max > dp[i] ? max : dp[i];
            }
        }

    }

    return max;
}

void test1() {
    int nums[] = {10, 9, 2, 5, 3, 7, 101, 18};
    printf("4=%d\n", lengthOfLIS(nums, 8));
}

void test2() {
    int nums[] = {10, 9, 8, 7, 6, 5, 4, 3};
    printf("1=%d\n", lengthOfLIS(nums, 8));
}

void test3() {
    int nums[] = {1,2,4,3,10,3,2,11};
    printf("5=%d\n", lengthOfLIS(nums, 8));
}

void test4() {
    int nums[] = {1, 2, 3, 4, 5, 6, 7, 8, 9};
    printf("9=%d\n", lengthOfLIS(nums, 9));
}

int main() {

    test1();
    test2();
    test3();
    test4();
}